home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2001 May / SGI IRIX Base Documentation 2001 May.iso / usr / share / catman / p_man / cat3 / librw / RWBTree.z / RWBTree
Encoding:
Text File  |  1998-10-30  |  12.1 KB  |  331 lines
  1.  
  2.  
  3.  
  4. RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                                    RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  5.  
  6.  
  7.  
  8. NNNNaaaammmmeeee
  9.      RWBTree - Rogue Wave library class
  10.  
  11. SSSSyyyynnnnooooppppssssiiiissss
  12.               #include <rw/btree.h>
  13.  
  14.  
  15.  
  16.               RWBTree a;
  17.  
  18.  
  19.  
  20.  
  21. DDDDeeeessssccccrrrriiiippppttttiiiioooonnnn
  22.      Class RRRRWWWWBBBBTTTTrrrreeeeeeee represents a group of ordered elements, not accessible by
  23.      an external key.  Duplicates are not allowed.  An object stored by class
  24.      RRRRWWWWBBBBTTTTrrrreeeeeeee must inherit abstract base class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee -- the elements
  25.      are ordered internally according to the value returned by virtual
  26.      function ccccoooommmmppppaaaarrrreeeeTTTToooo(((()))) (see class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee).  This class has certain
  27.      advantages over class RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee.  First, the B-tree is automatically
  28.      bbbbaaaallllaaaannnncccceeeedddd.  (With class RRRRWWWWBBBBiiiinnnnaaaarrrryyyyTTTTrrrreeeeeeee, you must call member function
  29.      bbbbaaaallllaaaannnncccceeee(((()))) explicitly to balance the tree.)  Nodes are never allowed to
  30.      have less than a certain number of items (called the oooorrrrddddeeeerrrr).  The default
  31.      order is 50, but may be changed by resetting the value of the static
  32.      constant "oooorrrrddddeeeerrrr" in the header file <<<<bbbbttttrrrreeeeeeee....hhhh>>>> and recompiling.  Larger
  33.      values will result in shallower trees, but less efficient use of memory.
  34.      Because many keys are held in a single node, class RRRRWWWWBBBBTTTTrrrreeeeeeee also tends to
  35.      fragment memory less.
  36.  
  37. PPPPeeeerrrrssssiiiisssstttteeeennnncccceeee
  38.      Polymorphic
  39.  
  40. PPPPuuuubbbblllliiiicccc CCCCoooonnnnssssttttrrrruuuuccccttttoooorrrrssss
  41.               RRRRWWWWBBBBTTTTrrrreeeeeeee();
  42.  
  43.  
  44.      Construct an empty B-tree.
  45.  
  46.               RRRRWWWWBBBBTTTTrrrreeeeeeee(const RWBTree& btr);
  47.  
  48.  
  49.      Construct self as a shallow copy of bbbbttttrrrr.
  50.  
  51.               Public Destructor
  52.           virtual
  53.           ~RRRRWWWWBBBBTTTTrrrreeeeeeee();
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                                    RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  71.  
  72.  
  73.  
  74.      Redefined from RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Calls cccclllleeeeaaaarrrr(((()))).
  75.  
  76. PPPPuuuubbbblllliiiicccc MMMMeeeemmmmbbbbeeeerrrr OOOOppppeeeerrrraaaattttoooorrrrssss
  77.               void
  78.           ooooppppeeeerrrraaaattttoooorrrr====(const RWBTree& btr);
  79.  
  80.  
  81.      Set self to a shallow copy of bbbbttttrrrr.
  82.  
  83.               RWBoolean
  84.           ooooppppeeeerrrraaaattttoooorrrr<<<<====(const RWBTree& btr) const;
  85.  
  86.  
  87.      Returns TTTTRRRRUUUUEEEE if self is a subset of bbbbttttrrrr.  That is, for every item in
  88.      self, there must be an item in bbbbttttrrrr that compares equal.  NNNNooootttteeee:  If you
  89.      inherit from RRRRWWWWBBBBTTTTrrrreeeeeeee in the presence of the Standard C++ Library, we
  90.      recommend that you override this operator and explicitly forward the
  91.      call.  Overload resolution in C++ will choose the Standard Library
  92.      provided global operators over inherited class members.  These global
  93.      definitions are not appropriate for set-like partial orderings.
  94.  
  95.               RWBoolean
  96.           ooooppppeeeerrrraaaattttoooorrrr========(const RWBTree& btr) const;
  97.  
  98.  
  99.      Returns TTTTRRRRUUUUEEEE if self and bbbbttttrrrr are equivalent.  That is, they must have the
  100.      same number of items and for every item in self, there must be an item in
  101.      bbbbttttrrrr that compares equal.
  102.  
  103. PPPPuuuubbbblllliiiicccc MMMMeeeemmmmbbbbeeeerrrr FFFFuuuunnnnccccttttiiiioooonnnnssss
  104.               virtual void
  105.           aaaappppppppllllyyyy(RWapplyCollectable ap, void*);
  106.  
  107.  
  108.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn to apply the user-supplied function
  109.      pointed to by aaaapppp to each member of the collection, in order, from
  110.      smallest to largest.  This supplied function should not do anything to
  111.      the items that could change the ordering of the collection.
  112.  
  113.               virtual RWspace
  114.           bbbbiiiinnnnaaaarrrryyyySSSSttttoooorrrreeeeSSSSiiiizzzzeeee() const;
  115.  
  116.  
  117.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  118.  
  119.               virtual void
  120.           cccclllleeeeaaaarrrr();
  121.  
  122.  
  123.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  124.  
  125.  
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                                    RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  137.  
  138.  
  139.  
  140.               virtual void
  141.           cccclllleeeeaaaarrrrAAAAnnnnddddDDDDeeeessssttttrrrrooooyyyy();
  142.  
  143.  
  144.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  145.  
  146.               virtual int
  147.           ccccoooommmmppppaaaarrrreeeeTTTToooo(const RWCollectable* a) const;
  148.  
  149.  
  150.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  151.  
  152.               virtual RWBoolean
  153.           ccccoooonnnnttttaaaaiiiinnnnssss(const RWCollectable* target) const;
  154.  
  155.  
  156.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  157.  
  158.               virtual size_t
  159.           eeeennnnttttrrrriiiieeeessss() const;
  160.  
  161.  
  162.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  163.  
  164.               virtual RWCollectable*
  165.           ffffiiiinnnndddd(const RWCollectable* target) const;
  166.  
  167.  
  168.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  The first item that compares equal to
  169.      the object pointed to by ttttaaaarrrrggggeeeetttt is returned or nnnniiiillll if no item is found.
  170.  
  171.               virtual unsigned
  172.           hhhhaaaasssshhhh() const;
  173.  
  174.  
  175.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  176.  
  177.               unsigned
  178.           hhhheeeeiiiigggghhhhtttt() const;
  179.  
  180.  
  181.      Special member function of this class.  Returns the height of the tree,
  182.      defined as the number of nodes traversed while descending from the root
  183.      node to an external (leaf) node.
  184.  
  185.               virtual RWCollectable*
  186.           iiiinnnnsssseeeerrrrtttt(RWCollectable* c);
  187.  
  188.  
  189.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Inserts the item cccc into the
  190.      collection and returns it. The item cccc is inserted according to the value
  191.      returned by ccccoooommmmppppaaaarrrreeeeTTTToooo(((()))).  If an item is already in the collection which
  192.  
  193.  
  194.  
  195.                                                                         PPPPaaaaggggeeee 3333
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202. RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                                    RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  203.  
  204.  
  205.  
  206.      iiiissssEEEEqqqquuuuaaaallll to cccc, then the old item is returned and the new item is not
  207.      inserted.  Otherwise returns nnnniiiillll if the insertion was unsuccessful.
  208.  
  209.               virtual RWClassID
  210.           iiiissssAAAA() const;
  211.  
  212.  
  213.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee to return ________RRRRWWWWBBBBTTTTRRRREEEEEEEE.
  214.  
  215.               virtual RWBoolean
  216.           iiiissssEEEEmmmmppppttttyyyy() const;
  217.  
  218.  
  219.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  220.  
  221.               virtual RWBoolean
  222.           iiiissssEEEEqqqquuuuaaaallll(const RWCollectable* a) const;
  223.  
  224.  
  225.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  226.  
  227.               virtual size_t
  228.           ooooccccccccuuuurrrrrrrreeeennnncccceeeessssOOOOffff(const RWCollectable* target) const;
  229.  
  230.  
  231.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Returns the number of items that
  232.      compare equal to ttttaaaarrrrggggeeeetttt.  Since duplicates are not allowed, this function
  233.      can only return 0 or 1.
  234.  
  235.               virtual RWCollectable*
  236.           rrrreeeemmmmoooovvvveeee(const RWCollectable* target);
  237.  
  238.  
  239.      Redefined from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.  Removes and returns the first item
  240.      that compares equal to the object pointed to by ttttaaaarrrrggggeeeetttt.  Returns nnnniiiillll if
  241.      no item was found.
  242.  
  243.               virtual void
  244.           rrrreeeemmmmoooovvvveeeeAAAAnnnnddddDDDDeeeessssttttrrrrooooyyyy(const RWCollectable* target);
  245.  
  246.  
  247.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  248.  
  249.               virtual void
  250.           rrrreeeessssttttoooorrrreeeeGGGGuuuuttttssss(RWvistream&);
  251.           virtual void
  252.           rrrreeeessssttttoooorrrreeeeGGGGuuuuttttssss(RWFile&);
  253.           virtual void
  254.           ssssaaaavvvveeeeGGGGuuuuttttssss(RWvostream&) const;
  255.           virtual void
  256.           ssssaaaavvvveeeeGGGGuuuuttttssss(RWFile&) const;
  257.  
  258.  
  259.  
  260.  
  261.                                                                         PPPPaaaaggggeeee 4444
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268. RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))                                                    RRRRWWWWBBBBTTTTrrrreeeeeeee((((3333CCCC++++++++))))
  269.  
  270.  
  271.  
  272.      Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttiiiioooonnnn.
  273.  
  274.               RWStringID
  275.           ssssttttrrrriiiinnnnggggIIIIDDDD();
  276.  
  277.  
  278.      (acts virtual) Inherited from class RRRRWWWWCCCCoooolllllllleeeeccccttttaaaabbbblllleeee.
  279.  
  280.  
  281.  
  282.  
  283.  
  284.  
  285.  
  286.  
  287.  
  288.  
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.                                                                         PPPPaaaaggggeeee 5555
  328.  
  329.  
  330.  
  331.